home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16614 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: seagoon.newcastle.edu.au!usenet
  2. From: mazz@faceng.newcastle.edu.au (Richard Mazzaferri)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: Thu, 11 Apr 1996 14:09:12 GMT
  6. Organization: Newcastle University
  7. Message-ID: <316c78c8.3816674@news.newcastle.edu.au>
  8. References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k4unk$15qe@sol.caps.maine.edu> <4k680p$6fs@longwood.cs.ucf.edu> <4k6hdg$5ob@blackice.winternet.com> <316b7b66.13881382@news.newcastle.edu.au> <4kgck5$98v@blackice.winternet.com>
  9. NNTP-Posting-Host: tesla.newcastle.edu.au
  10.  
  11. jdege@winternet.com (Jeff Dege) wrote:
  12.  
  13. > On Wed, 10 Apr 1996 09:16:03 GMT, Richard Mazzaferri (mazz@faceng.newcastle.edu.au) wrote:
  14. > : 
  15. > : Which of course (disregarding the fact that the algorithm fails to sort its
  16. > : inputs at all) is O(n) - much slower than the claimed O(2log n) algorithm
  17. > : :-)
  18. > 
  19. >     There's no such thing as O(2log n).  Constant factors are removed in
  20. > big-O notation.  So if you ever see O(2log n) you can assume that the
  21. > writer either made a type, or doesn't know what he's talking about.
  22.  
  23. You are correct.  I didn't want to complicate the issue by cleaning up the
  24. constant factor because that would weaken my reference to the "fastest"
  25. sorting algorithm claim made by another poster.
  26.  
  27. >    Meanwhile, the tricksort produces sorted output, which is all the spec
  28. > (incorrectly) requires.
  29.  
  30. My point was that this spec fails to solve the problem of the original
  31. poster - which is to sort a list of items, not to produce a (trivial) list
  32. of sorted items unrelated to the input.  Sure, TrickSort lives up to its
  33. own spec, but not the spec of the original problem.
  34.  
  35. Have fun,
  36.     Mazz.
  37. mazz@faceng.newcastle.edu.au
  38.